\chapter{Implementace}
Kapitola pojednává o samotné implementaci aplikace Visaulizer resp. její části XPathPlugin. Zbylé části implementace vycházejí ze zvolené formy aplikace. V případě hlubšího zájmu je možno čerpat další informace ve zdrojovém kódu.

Cílem práce bylo vytvořit vhodný parser XPath dotazů, který rozloží složitější XPath dotaz na jednodušší poddotazy. V programu Visualizer je použito XPath enginu frameworku .NET 3.5 a dalších tříd ze jmenného prostoru System.Xml.

Část XPathPlugin z velké části data cashuje. Cashování zaručuje, že výpočet je prováděn pouze jednou nebo v případě změny XPath dotazu.

\begin{figure}[h]
\begin{center}
\includegraphics[width=16cm]{figures/xpath-plugin1.png}
\caption{Implementace aplikace}
\label{fig:xpath_impl}
\end{center}
\end{figure}

\section{Algoritmy pro implementaci XPath parseru}
Základní myšlenkou každého textového parseru je rozložit patřičný text na jeho atomickou podobu v daném kontextu jazyka. Tuto skutečnost lze modelovat na příkladu parseru slov, kde bude atomická podoba představovat jednotlivá slova. V případě XPath jazyka je věc o~něco složitější...

Při implementaci parsovacího algoritmu jazyka XPath bylo zamýšleno se inspirovat stáva-\\
jícími algortimy, které tuto problematiku řeší. Avšak algortimus rozkládájící XPath dotaz na atomické výrazy nebyl nalezen. Existují XPath procesory, které tuto problematiku řeší např. procesor XALAN\footnote{XALAN - \href{XALAN}{http://xml.apache.org/xalan-j}} společnosti Apache Foundation nebo procesor SAXON\footnote{SAXON - \href{SAXON}{http://saxon.sourceforge.net}}. Ná základě tohoto faktu se implementace aplikace Visualizer ubírala vytvořením vlastních algoritmů pro~parsovaní XPath jazyka.

\section{Jmenný prostor System.Xml}
Tento jmenný prostor umožňuje práci s XML dokumenty (\emph{načítání, validaci, ukládání, práci s uzly atd.}), XPath jazykem a dalšími prvky.

\begin{figure}[h]
\includegraphics[width=16cm]{figures/system-xml.png}
\caption{Jmenný prostor System.Xml}
\label{fig:system_xml}
\end{figure}

\subsection{XmlDocument}
Tato třída obsahuje základní prvky pro práci s XML dokumentem jako je načítání XML ze~souboru, uložení XML do souboru a další vlastnosti definované standardem W3C DOM 3.0.

Po načtení XML dokumentu vytvoří tato třída jeho DOM reprezentaci. Vybírat uzly lze prostřednictvím definice konkrétního uzlu metodou \verb GetElementById  nebo XPath dotazem metodou \verb SelectNodes. Výběr uzlů pomocí XPath dotazu je použitý v aplikaci Visualizer.

\subsection{XmlNodeList}
Tato třída obsahuje kolekci uzlů vybraných patřičnou metodou třídy \verb XmlDocument. Důležitým poznatkem je, že jednotlivé uzly odkazují na instance uzlů reprezentovaných DOMem XML dokumentu a změna těchto uzlů se ihned projeví na DOM reprezentaci tohoto dokumentu.

\subsection{XPath.XPathExpression}
Třída XPathExpression slouží pro kompilací dotazů jazyka XPath. Vyhodnocuje také validitu XPath výrazu. Pro nevalidní XPath dotaz vytvoří třída vyjímku typu \verb XPathException .

Výběr uzlů pomocí kompilovaného výrazu je podstatně rychlejší než pomocí čistě textového dotazu.


\section{Načtení a zobrazení XML souboru}
Pro zobrazení množiny uzlů vybraných na základě XPath dotazu je potřeba tyto uzly vhodně zobrazit. Pro zobrazení uzlů a podporu funkce breakpoint bylo potřeba vytvořit nový grafický prvek zvaný \verb TreeListView .

Objekt typu \verb TreeListView  je složený ze dvou standardních prvků obsažených v technologii WPF a sice \verb TreeView  a \verb ListView . Díky této skutečnosti podporuje tento prvek zobrazení sloupců a také je schopen zobrazit hierarchickou strukturu. Pro zobrazení hierarchické struktury bylo potřeba vytvořit ještě prvek typu \verb TreeListViewItem .

\noindent
Prvku \verb TreeListViewItem  lze nastavit tyto vlastnosti:
\begin{itemize}
\item hodnota breakpointu (\emph{true, false})
\item číslo řádku
\item textový obsah prvku
\end{itemize}

\subsection{Načtení XML souboru}
Při výběru souboru zachytává část Core událost \verb FileOk  dialogového okna \verb OpenFileDialog . Při zpracování této události se aktivnímu pluginu nastaví cesta ke zvolenému souboru a~zavolá se metoda \verb Show() , definovaná rozhraním \verb IPlugin .

\subsection{Zobrazení XML dokumentu}
Při zavolání metody \verb Show()  implementovanou částí XPathPlugin se spustí procesy, které otestují a případně zobrazí zvolený soubor. Je-li soubor podporovaný, jedná-li se o well-formed XML dokument, vytvoří se z tohoto dokumentu jeho objektový model DOM. Při zobrazování se odehrávají dva děje. Postupně se zobrazí všechny uzly objektu DOM a~zároveň probíhá mapování těchto uzlů na uzly \verb TreeListViewItem  zobrazených v komponentě \\\verb TreeListView . Při převodu uzlu, obsaženého v DOMu, na jeho textovou podobu je zapotřebí tento text generovat.

\noindent
Textová podpoba každého takového uzlu je následující:
\begin{itemize}
\item je-li uzel typu element, začíná-li uvozovací a končí koncovou značkou, je vygenerováno jméno uzlu s případným prefixem a jména a hodnot všech atributů
\item je-li uzel jiného typu, vygeneruje se jeho vnitřní text, tedy text, který je obsažen v těle tohoto uzlu
\end{itemize}

\section{Parsování a transformace dotazu XPath}
Parsování a následná transformace prvků XPath je nejdůležitější součástí části XPathPlugin. V následujících podkapitolách jsou popsány děje, kterých je potřeba pro správný chod programu.
\clearpage
\subsection{XPathExpressionNormalizer}
Tato třída normalizuje XPath dotaz. Normalizace dotazu se děje ve dvou krocích. Prvním krokem je odstranění nadbytečných mezer z dotazu. Tuto funkcí řeší následující cyklus:

\begin{figure}[!h]
\begin{lstlisting}[frame=single]
foreach(char symbol in expression.ToCharArray())
{
    if (symbol == '\'' || symbol == '"')
    {
        if (quote == '\0')
        {
            quote = symbol;
            isSyntax = false;
        }
        else if (symbol == quote)
        {
            quote = '\0';
            isSyntax = true;
        }
   	}
    if (isSyntax && (!IsWhiteSpace(symbolBefore) ||
                     !IsWhiteSpace(symbol))
       )
        proccessedExpression += symbol;

    else if (!isSyntax)
        proccessedExpression += symbol;

   	symbolBefore = symbol;
}
\end{lstlisting}
\label{fig:mezery}
\caption{Cyklus odstraňující nadbytečné mezery}
\end{figure}

\noindent
Z počátku byl užit regulární výraz \verb \s+, který nahrazoval nadbytečné mezery. Ovšem tento výraz nahrazoval nadbytečné mezery i v textu uvozeném znaky \verb '  nebo \verb "  , což je nepřípustné. Z tohoto důvodu byl regulární výraz nahrazen.

Druhým krokem je odstranění nadbytečných kulatých závorek. Výraz, ve kterém mohou být závorky odstraněný, musí začínat levou \verb (  a končit pravou \verb )  závorkou. Tuto funkci implementuje následující sekvence kódu:
\begin{figure}[!h]
\begin{lstlisting}[frame=single]
expression = expression.Trim();
bool canRemoveParens = expression.StartsWith("(") &&
                       expression.EndsWith(")");
while (canRemoveParens)
{
    expression = expression.Substring(1, expression.Length - 2)
                           .Trim();
    canRemoveParens = expression.StartsWith("(") &&
                      expression.EndsWith(")");
}

\end{lstlisting}
\label{fig:zavorky}
\caption{Cyklus odstraňující nadbytečné závorky}
\end{figure}

\subsection{XPathExpressionParser}
Tato třída implementuje parsování dotazu XPath na vhodné poddotazy, ze kterých vytváří strom poddotazů.

\noindent
Prvním krokem pro parsování XPath dotazu je jeho normalizace. Tyto prvky implementuje třída XPathExpressionNormalizer popsaná výše. V dalším kroku přichází parsování dotazu.

\subsubsection{Parsovací vrstva}
Každý XPath dotaz začíná na vrstvě číslo 1. Při postupném zpracovávání znaků dotazu jsou tyto znaky kontrolovány na přítomnost kulaté nebo hranaté závorky, která není uvozena znaky \verb '  nebo  \verb " . Každá kulatá nebo hranatá levá závorka zvýší parsovací vstvu o jeden stupeň. Tato nová parsovací vrstva začíná právě jeden znak za touto levou závorkou. Každá kulatá nebo hranatá pravá závorka sníží aktuální parsovací vrstvu o jeden stupeň. Tato snížená parsovací vstva začíná už touto pravou závorkou.

Zavedením parsovací vrstvy a parsováním na úrovni parsovací vrstvy číslo 1 je jednak ošetřena možnost záměny kulatých závorek přítomných u funkce a závorek značících sloučení dotazu a dále je také docíleno správného procházení XPath dotazem.

Procházení dotazem si lze představit na příkladu slupek - je-li zapotřebí přejít např. o~dvě vrstvy níže, musí se nejprve tyto vrtsvy celé projít jedna po druhé. Toto přirovnání lze demonstrovat na takovémto XPath dotazu:
\begin{verbatim} //node-name[. = /*[3]] \end{verbatim}
V tomto dotazu je cílem získat obsah predikátu náležícího uzlu \verb node-name . Parsování na~vrstvě číslo 1 zajistí, že obsah tohoto predikátu bude vrácen v kýžené podobě:
\begin{verbatim} [. = /*[3]] \end{verbatim}

\subsubsection{Parsování znaků}
Každý dotaz je rozložen na jednotlivé znaky. Těmto znakům je přiřazen jejich význam, který je uveden v následující tabulce \ref{tab:vyznam_znaku}:
\begin{center}
\begin{longtable}{|c|l|}
\hline
\textbf{Význam znaku}   & \textbf{Popis} \\
\hline
\endfirsthead
\multicolumn{2}{c}%
{{\bfseries \tablename\ \thetable{} -- pokračování z předchozí stránky}} \\
\hline
\textbf{Význam znaku}   & \textbf{Popis} \\
\hline
\endhead
\hline
\multicolumn{2}{|r|}{{Pokračování na další stránce}} \\
\hline
\endfoot
\endlastfoot\hline
Syntax                  & znak, který neodpovída ani jednomu významu níže \\
\hline
Slash                   & \verb /  lomítko \\
\hline
DoubleSlash             & \verb //  dvojité lomítko \\
\hline
Union                   & \verb |  pipe \\
\hline
LeftParenthesis         & \verb (  levá kulatá závorka \\
\hline
RightParenthesis        & \verb )  pravá kulatá závorka \\
\hline
LeftSquareParenthesis   & \verb [  levá hranatá závorka \\
\hline
RightSquareParenthesis  & \verb ]  pravá hranatá závorka \\
\hline
Comparator              & znaky \verb <, \verb >,  \verb =,  \verb <=,  \verb >=, \verb != \\
\hline
Quote                   & znaky \verb '  a \verb " ~\\
\hline
WhiteChar               & jakýkoliv bílý znak - mezera, nový řádek, tabulátor \\
\hline
String                  & znak uvozený ve znacích typu \verb Quote \\
\hline
End                     & koncový znak \verb \0 \\
\hline
\caption{Význam znaků pro XPathExpressionParser}
\label{tab:vyznam_znaku}
\end{longtable}
\end{center}

\subsubsection{Parsování dotazu}
Všechny XPath dotazy a jejich poddotazy se \textbf{parsují na parsovací vrstvě číslo 1} postupným zpracováváním jejich znaků. Tyto dotazy se rozkládají podle těchto pravidel:
\begin{itemize}
\item rozložení dotazu podle znaku \textbf{\vline}
\item rozložení dotazu podle znaku \verb /  nebo \verb // ~
\item rozložením dotazu na \verb|test uzlu| a případné predikáty
\end {itemize}

\noindent
Tabulka \ref{tab:stavy_pa} popisuje stavy parsovacího automatu, kterých se využívá pro parsování dotazu:
\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|l|}
\hline
\textbf{Význam znaku}   & \textbf{Popis} \\
\hline
ParseUnion              & parser hledá přítomnost znaku \verb |  \\
\hline
ParseExpression         & parser hledá přítomnost znaků \verb /  a  \verb //  \\
\hline
\end{tabular}
\caption{Stavy parsovacího automatu XPathExpressionParser}
\label{tab:stavy_pa}
\end{center}
\end{table}

Při inicializaci se parsovací automat nastaví do stavu \verb|ParseUnion|, ve kterém se hledá výskyt znaku \verb | . V dalším kroku se parsovací automat přepne do stavu \verb|ParseExpression|, ve kterém se hledá přítomnost znaku \verb /  nebo \verb // . V posledním kroku se vyhodnocují nalezené poddotazy.

\noindent
Vyhodnocování dotazů se dějě ve dvou částech. V prvním částí se dotazu přiřadí jeho typ, který je následně zpracován.
\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|l|}
\hline
\textbf{Typ dotazu} & \textbf{Popis} \\
\hline
Single              & jednoduchý dotaz, který splňuje podmínku, že není žádného \\
                    & jiného typu \\
\hline
MultiElement        & dotaz složený z více znaků \verb /  nebo  \verb //  \\
\hline
Grouping            & dotaz, který začíná a končí kulatými závorkami \verb (,)  \\
\hline
Union               & dotaz, který obsahuje znak \verb |  \\
\hline
SingleFilter        & jenoduchý dotaz, který splňuje podmínku, že není jiného typu \\
                    & a obsahuje právě jeden predikát \\
\hline
MultiFilter         & jednoduchý dotaz, který splňuje podmínku, že není jiného typu  \\
                    & a obsahuje více predikátů \\
\hline
\end{tabular}
\caption{Typy XPath dotazů}
\label{tab:typ_vyrazu}
\end{center}
\end{table}

Podle vyhodnoceného typu výrazu se vykoná jedna z následujících akcí:
\begin{itemize}
\item pro typ dotazu \verb Single  parsování skončí
\item pro typy dotazu \verb MultiElement , \verb Grouping  nebo \verb Union  se výraz znovu rekursivně parsuje
\item pro typy dotazu \verb SingleFilter  nebo \verb MultiFilter  se výraz zpracuje s požadavkem parsovat predikát
\end{itemize}

\subsubsection{Parsování predikátu}
Při zkoumání predikátu se hledají řetězce \verb and  nebo \verb or  obsažené v první parsovací vrstvě predikátu - \emph{v tomto případě se vypouštějí první} \verb [  \emph{závorka a poslední} \verb ]  \emph{závorka}. Při výskytu těchto řetězců se text predikátu podle nich rozloží.

Parsování predikátu není rekursivní - rozklad se děje pouze při prvním průchodu. Z toho vyplývá, že pokud predikát neobsahuje v první parsovací vrstvě řetězece \verb and  nebo \verb or , není již dále zpracován. Nerekursivnost je zavedena z důvodu lepší čitelnosti parsovaného dotazu.

\subsubsection{Strom dotazů}
\label{ssec:strom-dotazu}
Do \verb|stromu dotazů| se přidávají zpracované uzly XPath dotazu, které prošly procesem parsování.
\noindent
Uzly se přidávají v následujícím pořadí:
\begin{itemize}
\item uzly složitejšího charakteru - např. uzavřené kulatými závorkami
\item uzly rozdělené podle znaku \vline
\item uzly rozdelené podle znaků \textbf{/, //}
\item uzly obsahující predikáty
    \begin{itemize}
    \item uzel s částí \verb|test uzlu|
    \item uzel se samotným predikátem
        \begin{itemize}
        \item predikátový uzel rozdělený podle řetězců \textbf{and} nebo \textbf{or}
        \end{itemize}
    \end{itemize}
\end{itemize}

\noindent
Následující \verb|strom dotazů| je zobrazen pro XPath dotaz:
\begin{verbatim}/expr1/expr2[@id = "2" or @cd = "d"] | //*/@name\end{verbatim}

\begin{figure}[h]
\includegraphics[width=16cm]{figures/strom.png}
\caption{Strom dotazů vytvořený XPathExpressionParserem}
\label{fig:strom_dotazu}
\end{figure}

Každý uzel takto vytvořeného stromu nese kromě samotného výrazu také informaci o~typu uzlu a typem spojení s následujícím uzlem. Tyto typy jsou popsány následujícími dvěma tabulkami \ref{tab:typ_uzlu} a \ref{tab:typ_spojeni}.

\begin{table}[!h]
\begin{center}
\begin{tabular}{|c|l|}
\hline
\textbf{Typ uzlu}   & \textbf{Popis} \\
\hline
Expression          & uzel, který splňuje podmínku, že není jiného typu \\
\hline
Filter              & predikátový uzel \\
\hline
FilterInside        & uzel, který obsahuje vnitřní hodnotu predikátu \\
\hline
\end{tabular}
\caption{Typy uzlů XPath stromu}
\label{tab:typ_uzlu}
\end{center}
\end{table}


\begin{table}[!h]
\begin{center}
\begin{tabular}{|c|l|}
\hline
\textbf{Typ spojení s následujícím uzlem}   & \textbf{Popis} \\
\hline
Default                                     & uzel standardně spojený s následovníkem \\
                                            & (\emph{záleží na kontextu}) \\
\hline
Union                                       & uzel typu Expression spojený s následovníkem \\
                                            & znakem  \verb |  \\
\hline
And                                         & uzel typu FilterInside spojený s následovníkem \\
                                            & logickou hodnotou \verb and  \\
\hline
Or                                          & uzel typu FilterInside spojený s následovníkem \\
                                            & logickou hodnotou \verb or  \\
\hline
\end{tabular}
\caption{Typy spojení uzlu s jeho následovníkem v XPath stromu}
\label{tab:typ_spojeni}
\end{center}
\end{table}


\subsection{XPathTreeTransformer}
Tato třída přebírá od třídy XPathParser XPath \verb|strom dotazů| a vhodným způsobem zpětně sestavuje XPath dotazy a zároveň mapuje tyto dotazy na uživatelem zadaný XPath dotaz.

Transformace stromu dotazů je implementována procházením tohoto stromu do hloubky metodou postorder. Dotazy a mapování se tedy sestavují od jednodušších ke složitějším.

\subsubsection{Sestavování dotazů}
Pro danný uzel vybraný ze \verb|stromu dotazů| se zpětně vytvoří XPath dotaz následujícím způsobem:
\begin{enumerate}
\item vytvoří se prázdný dotaz označený jako X
\item dotaz Y se staví spojením všech výrazů levých sourozenců daného uzlu
    \begin{enumerate}
    \item pokuď se jedná o první iteraci, připojí se k dotazu i výraz daného uzlu
    \end{enumerate}
\item před dotaz X se připojí sestavený dotaz Y
\item danému uzlu se nastaví hodnota jeho rodiče a opakuje se krok 2. Kořenovým uzlem tato iterace končí
\end{enumerate}

\clearpage
\subsubsection{Mapování dotazů}
Mapování vždy začíná na začátku celého dotazu. Pro danný uzel vybraný ze \verb|stromu dotazů| se vytvoří mapování takto:
\begin{enumerate}
\item vytvoří se pole uzlů
    \begin{enumerate}
    \item do pole se přidá daný uzel a všichni jeho praví sourozenci
    \item daném uzlu se přiřadí hodnota jeho rodiče a opakuje se krok 1a. Kořenovýn uzlem tato iteracekončí
    \end{enumerate}
\item pole uzlů se převrátí, tak aby začínalo kořenovým uzlem
\item při procházení pole se postupně lokalizuje daný uzel zkracováním textu, ve které se může jeho hodnota nacházet
\item vytvoří se mapování
\end{enumerate}

Speciálním případem jsou kulaté a hranaté závorky. Musí se brát ohled na to, že daný uzel resp. jeho výraz může být vnořený v predikátu nebo ve slučovacích kulatých závorkách. Pro tyto závorky se  mapování vytváří při stejné iteraci průchodu polem.

\noindent
Obrázek ukazuje výsledek transformace \verb|stromu dotazů| pro XPath dotaz uvedený v sekci \ref{ssec:strom-dotazu} \nameref{ssec:strom-dotazu}:
\begin{figure}[!h]
\begin{center}
\includegraphics[width=10cm]{figures/strom-dotazu.png}
\caption{Transformace XPath stromu dotazů}
\label{fig:transformace}
\end{center}
\end{figure}

\clearpage
\section{Zvýrazňování XPath dotazů}
Po transformaci XPath dotazu přichází na řadu grafické znázornění poddotazů vzniklých při transformaci a to jak v samotném XPath dotazu tak na množině zobrazených uzlů. O~zvýrazňování se stará komponenta \verb|XPathHighlighter|, která z části XPathPlugin přebírá již vytvořené mapování XPath poddotazů a jejich vyhodnocenou množinů XML uzlů, dále také mapování XPath poddotazů a jejich ekvivalentu v textovém boxu, který obsahuje uživatelem zadaný XPath dotaz.

\noindent
Úlohy, které je potřeba pro zvýraznění vykonat, jsou následující:
\begin{itemize}
\item smazat veškeré předchozí zvýraznění
\item vybrat příslušný XPath poddotaz
\item pro tento XPath poddotaz obarvit
    \begin{itemize}
    \item text
    \item prvky \verb|TreeListViewItem|
    \end{itemize}
\end{itemize}

Při obarvování prvků \verb|TreeListViewItem| se bere zřetel na přítomnost zapnutého breakpointu. Je-li uzel s aktivovaným breakpointem obarvován, obarví se červeně a nastaví se mu fokus. 